import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;

//思想：最大堆
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
        ArrayList<Integer> result = new ArrayList<>();
        if(k > input.length || input == null || input.length ==0 || k == 0) return result;
        
        //构建优先级队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new Comparator<Integer>(){
            //重写compare方法
            public int compare(Integer o1, Integer o2){
                return o2  - o1;     //return o2.compareTo(o1)也可
            }
        });
        
        //保持堆的大小为k，每次只和堆顶比较，如果比堆顶小，则移除堆顶元素，将新元素入堆
        for(int i = 0; i < input.length; i++){
            if(queue.size() < k){
                queue.offer(input[i]);
            }else if(input[i] < queue.peek()){
                queue.poll();
                queue.offer(input[i]);
            }
        }
        
        //将堆中数据依次放在result中
        while(!queue.isEmpty()){
            result.add(queue.poll());
        }
        return result;
    }
}